Why Postfix? The Shunting-Yard Algorithm
Human-readable Infix notation (e.g., A + B * C) requires complex rules like operator precedence, parentheses, and associativity for unambiguous evaluation. Postfix notation (e.g., A B C * +) is inherently unambiguous, making it ideal for stack-based machine evaluation because the order of operations is fixed by operand placement.
The conversion process, known as the Shunting-Yard Algorithm (Dijkstra), uses a single Operator Stack and an Output Queue (or list) based on three core rules:
- Operands: Immediately move operands (variables, numbers) to the Output Queue.
- Parentheses: An opening parenthesis
(is pushed onto the Operator Stack. A closing parenthesis)forces popping all operators from the stack to the output until the corresponding(is found (which is then discarded). - Operators: Pop operators from the Stack to the Output Queue if the stack top has higher or equal precedence than the current operator. Then, push the current operator onto the stack.
Algorithm Efficiency
The efficiency of the conversion algorithm depends directly on the linear traversal of the input expression.
| Metric | Time Complexity | Space Complexity |
|---|---|---|
| Shunting-Yard (Infix $\to$ Postfix) | $O(N)$ | $O(N)$ (For output and stack) |
| Reasoning | Each token (N tokens total) is read once, pushed onto the stack/output at most once, and popped at most once. This ensures linear time complexity. Space is required to store the resulting Postfix string (Output Queue) and the intermediate operators on the Operator Stack. | |
Key Rule: Operator Precedence
The core challenge lies in handling operator priorities. We define precedence levels to manage the stack state:
| Operator | Precedence Level | Associativity |
|---|---|---|
| ^ (Power) | 3 | Right |
| *, / | 2 | Left |
| +, - | 1 | Left |
| ( ) | Highest | N/A |
CRITICAL HINT: For Left Associative operators (like + and -), if the current operator has the same precedence as the operator on the stack top, the stack operator must be popped first to maintain left-to-right grouping.
1. Convert the following Infix expression into Postfix notation: $$\mathbf{A * (B + C)}$$
2. What is the postfix form of the expression A + B - C, considering left-associativity?
3. In the Shunting-Yard algorithm, what is the primary purpose of the operator stack?
4. When a closing parenthesis ) is read from the input, what is the correct procedure?